// Created by WXX on 2021/11/29 21:31
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 典型的区间覆盖问题
class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int time) {

        sort(clips.begin(), clips.end(), [&](vector<int> &a, vector<int> &b) {
            return a[0] < b[0];
        });
        int res = 0, last = 0;  // last: 上一次覆盖到的最远的位置
        for (int i = 0; i < clips.size(); ) {
            if (clips[i][0] > last) return -1;

            // 找到区间左端点小于last的最靠右的端点
            int r = 0;
            while (i < clips.size() && clips[i][0] <= last) {
                r = max(r, clips[i][1]);
                i++;
            }

            last = r;
            res++;
            if (last >= time) break;
        }
        if (last >= time) return res;
        return -1;
    }
};

int main() {

    vector<vector<int>> clips = {{0, 4}, {2, 8}};
    cout << Solution().videoStitching(clips, 5) << endl;

    return 0;
}
